package Arrays;

public class 二分查找 {
    /*
    二分查找
    折半的条件： min<=max
    前提: 数组元素必须是排好序的
思路:
1. 定文两个变量记录最小索引，和最大素引2. 折半的动作不止一次，应该使用循环
条件 mhile(min <= max)
3。循环中计算出中间紫引
4，加入判断
元素如果大于中间元素 : min = mid + 1;
元素如果小于中间元素 : max = mid - 1;
元素如果等于中间元素 : 将索引返回 (mid)
     */
    public static void main(String[] args) {
        int[] arr = {11,22,33,44,55,66,77,88,99,100};

       int index = binarySearch(arr,111);
        System.out.println(index);
    }
    private static int binarySearch(int[] arr, int num){
        //定义俩个变量记录最小索引和最大索引
        int min = 0;
        int max = arr.length-1;
        int mid; //中间索引
        // 2折半的动作不止一次，应该使用循环
        while (min<=max){
            //3 计算中间索引
            mid = (min+max)/2;
            // 4 对此
            if (num > arr[mid]){
                min = mid+1;
            }else if (num<arr[mid]){
                max = mid-1;
            }else {
                return mid;
            }
        }
        //走完代表没找到-1
        return -1;
    }
}
